1. Field of the Invention
This invention relates generally to the system architecture and data management techniques to configure and design a database searching and learning apparatus. More particularly, this invention relates to an improved database searching and learning system to speed up the database searching and learning processes for implementation in single chip Ethernet frame switching system. The database searching and learning processes can be completed within one or two clock cycles. Improved searching and learning process speed also enables a pipelined architecture for constructing systems to carry out database searching and learning processes.
2. Description of the Prior Art
As the Ethernet packet switch fabrics are now required to process gigabit per second, conventional technology is faced with a difficult challenge. The challenge is to perform an address resolution task at a rate of gigabits per second in order to be in synch with such a high data-rate in switching and transmission operation. Limited by the techniques available for address resolution, conventional methods are either too slow or too expensive. Practical application of Ethernet packet switch of higher data-rate is therefore hindered by this difficulty. In order to have better understanding of the technical background, the basic structure of the database entry items and the techniques employed for conducting an address resolution is explained first.
Database search logic is a technique applied to map the key of the searched item with the keys of all the items contained in a database. When a match is identified, the associated data in the database is retrieved as output. For a database employed for storing addresses for packet or cell switch, the database search logic is commonly referred to as lookup engine or address resolution logic. The database is generally referred to as an address table. FIG. 1 shows the structure of a database entry item, which typically comprises three parts. The first part is the key for identifying the item, e.g., an address. The second part is a status data for providing a state of this database entry item. The state of the item may be the data related to information such as validity, age and other control information. The third part is the data item itself. For an address table, the data item is the data associated with the address. For an Ethernet packet switching system, the data may be used as the value of a port number. Details for application of this data item in an Ethernet switching system will be further discussed below.
FIG. 2 shows the format of an Ethernet packet processed by an Ethernet switching system. The destination address (DA), is applied to identify the node to which the packet should be forwarded. The source address (SA) is included to indicate the address of the node from which the packed is sent out The lookup engine, i.e., an address resolution logic, for a switching fabric uses the DA as a key to find the destination port and the associated information related to the destination address if applicable. The source address (SA) is used by the automatic learning logic to establish the address table.
A typical Ethernet packet switch system is illustrated in FIG. 3. A data packet received from the media is converted into digital format by the physical layer device (PHY). A media access control (MAC) logic is responsible to retrieve the destination address (DA) data embedded in the packet and to pass the DA data as a key. The DA is used by the address resolution logic (ARL) as a key to search of the associated data item in the database. The database is an address table for this application. The ARL searches the address table to find the matched DA to retrieve a data item for providing an address of the destination port The destination port address is returned to the MAC. A request is then sent by the source MAC to the switch fabric to send the packet to the destination MAC. After receiving the packet, the destination MAC will forward the packet to the PHY for further transmission. For a gigabit Ethernet system, the rate for data transmission can be as high as 109 bits per second. For an Ethernet packet switching system with one ARL shared by 16 MAC ports, there can be as high as 23.8-million address resolution requests per second. Under a worst-scenario assumption, the frequency of lookup request for address resolution can reach as high as the calculated value of:
16* 109 bits/ [(512+64+96) bits]=23.8 *106 
Where 512 bits is the minimum packet length with a 64-bit preamble and 96 inter-packet gap. As will be further discussed below, in order to satisfy such a high-speed processing requirement, very expensive ARL system has to be implemented when conventional techniques are applied.
FIG. 4 is a functional block diagram of a conventional address resolution logic system. There are two basic modules, i.e., a lookup logic module and a learning logic module, for an ARL system. Upon receiving a lookup request, a database search is performed to locate a database entry item matched the destination address contained in the received packet Conventional database search techniques such as link list search and content addressable memory (CAM) search are further discussed below.
The structure of a traditional address table is a link-list type table. The keys are hashed into different xe2x80x9cbucketsxe2x80x9d. In each bucket, entries of the data items are chained together through a link list The link lists can be sorted or unsorted lists. FIG. 5 shows the linking configurations of the data entries in each bucket for a link list based address table. FIG. 6 is a flow chart showing the processing steps of an ARL system in conducting a database search on a link-list based address table. After a lookup request is received, the key is first hashed into a bucket number. The search begins by pointing to the first entry of the bucket and then comparing the key with that of the first entry of the bucket. A check is made to find out if the key matches with the data in the first entry. If the key matches, then the data is retrieved, if not, another check is made to determine if this is the last entry in a specific bucket If not, then the process is pointed to a next entry in the bucket and another attempt is performed to match the key with the data. If this data entry is the last entry is the last entry in the bucket, then a xe2x80x9cresult unknownxe2x80x9d is returned. In performing this search, for a sorted link list, a binary search algorithm can take up to log2N cycles where N is the length of the link list. For an unsorted link list, the search can take up N cycles. Similar to the lookup logic, the learning logic of the ARL system will also search if there is a match in the entry matched up with the key. As that shown in FIG. 7, the learning logic will also check if the data is changed when a matched key is identified. The data item in the database will be updated when there is a change in the data. If the key is not found in a bucket, the key and the data are added to the bucket in the learning process by the learning logic. Again, to update or insert a new database item, for a sorted link list, the learning process may take up log2N cycles, and for an unsorted link list, it may take up N-cycles. Due to these time-cycle requirement, the link-list based methodology as discussed above is obviously too slow when a system is implemented with high transmission data rate.
Another conventional method for establishing and searching a database is by employing a content address memory (CAM) technique. FIG. 8 is an organizational configuration of a content addressable memory based address table. The CAM based ARL system includes a comparand register for receiving and temporarily storing the key. The ARL system further includes n-comparators. The data stored in the comparand register is compared to the address entry in each of these n-comparators. A matched address is identified and retrieved from the memory as the output data of the search process. The lookup process of a CAM-based address table is shown in FIG. 9 and the learning process is shown in FIG. 10. With the CAM address table configuration and processing method, the lookup process takes up only one cycle. However, each data entry of the address table must be provided with an individual comparator. Not only the address table is more expensive due to the comparator requirement, also, the amount of address data that can be stored in such address table is more limited due to the space taken up by these comparators. In contrast to the lookup process, the learning process of the CAM-based address table has to find an empty space to store a new entry, Therefore, in addition to the operations performed by the comparators, the learning logic may take extra cycles to find the appropriate location to store a new data entry. Therefore, with the CAM-based address table, there is still no guaranty that the lookup and the learning processes can be completed in a single cycle due to the uncertainty of completion of a learning process for continuously updating the database.
Therefore, a need still exists in the art of local area network communication to provide a new and improved system configuration and database management techniques for carrying out the lookup and learning logic operations for completing the frame switching tasks to match up with the higher data transmission rate. It is desirable that a system can be provided with assurance that the lookup and learning processes can be completed within one or two dock cycles. It is further desirable that such system can be implemented at a lower cost then the currently available CAM based addressable technology. A high-speed ARL operation can be provided that without incurring very expensive hardware configuration as that implemented in current CAM based systems.
It is therefore an object of the present invention to provide an improved system configuration for performing completing the database searching and learning processes within one or two dock cycles such that the aforementioned difficulties and limitations in the prior art can be overcome.
Specifically, it is an object of the present invention to provide an improved system configuration and address table structure organized into a plurality of memory banks. Therefore, the database lookup and learning processes can be carried out by employing a plurality of comparators in parallel to compare the key with data items stored in specific bucket-slot from a plurality of memory banks. This two-dimensional memory slot array is therefore better organized for carrying out an instant access and key-identification. The difficulties encountered by conventional link-list or content based memory database can be overcome.
Another object of the present invention is to provide an improved system configuration and address table structure organized into a plurality of memory banks. The system configuration and address table organization is enabled to take advantage of the very wide data buses, which can be easily implemented inside a silicon chip. The improved database searching and learning system can therefore be conveniently implemented on a semiconductor chip.
Another object of the present invention is to provide an improved system configuration and address table structure organized into a plurality of memory banks. The database lookup and learning processes can be completed in a time-duration no more than two clock cycles. The improved system configuration and database organization can be suitable for cascading into pipeline configuration for high-speed lookup and learning processes.
Briefly, in a preferred embodiment, the present invention includes an address table apparatus that includes an address bus for receiving input data packets and for hashing a designated bucket number and extracting a key from each of the data packets. The address table apparatus further includes a plurality of memory banks connected to the address bus wherein each memory bank includes a plurality of memory buckets for storing a destination address (DA) and a port number in each of the buckets. The address table apparatus further includes a comparand bus connected to the address bus for receiving the key therefrom. The address table apparatus further includes a plurality of comparators each corresponding to one of the memory banks for receiving the destination address (DA) and the port number from the designated bucket from a corresponding memory bank. The comparators further connected to the comparand bus for receiving and comparing the key to the address from the designated bucket in each of the memory banks. The address table apparatus further includes a result bus connected to the comparators for displaying an output port number from one of the comparators if the key extracted from one the data packets matching the destination address (DA) from one of the designated buckets.
These and other objects and advantages of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiment which is illustrated in the various drawing figures.